//黄金矿工
class Solution {
public:
    int res=0;
    int m;
    int n;
    int arr[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
    vector<vector<bool>>used;
    int getMaximumGold(vector<vector<int>>& grid) 
    {
        m=grid.size();
        n=grid[0].size();
        used.resize(m,vector<bool>(n,false));
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]!=0)
                {
                    used[i][j]=true;
                    dfs(grid,i,j,grid[i][j]);
                    used[i][j]=false;
                }
            }
        }
        return res;
    }
    void dfs(vector<vector<int>>& grid,int x,int y,int sum)
    {
        res=max(res,sum);
        for(int i=0;i<4;i++)
        {
            int nx=x+arr[i][0];
            int ny=y+arr[i][1];
            if(nx<0 || nx>=m || ny<0 || ny>=n || used[nx][ny])continue;
            if(grid[nx][ny]==0) continue;

            used[nx][ny]=true;
            dfs(grid,nx,ny,sum+grid[nx][ny]);
            used[nx][ny]=false;            
        }
    }
};

//单词搜索
class Solution {
public:
    int arr[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
    vector<vector<bool>>used;
    int m;
    int n;
    bool exist(vector<vector<char>>& board, string word) 
    {
        m=board.size();
        n=board[0].size();
        used.resize(m,vector<bool>(n,false));
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(board[i][j]==word[0])
                {
                    used[i][j]=true;
                    if(dfs(board,word,1,i,j)) return true;
                    used[i][j]=false;
                }
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>>& board, string& word,int index,int x,int y)
    {
        if(index==word.size()) return true;

        for(int i=0;i<4;i++)
        {
            int nx=x+arr[i][0];
            int ny=y+arr[i][1];
            if(nx<0 || nx >=m || ny<0 || ny >=n || board[nx][ny]!=word[index]) continue;
            if(used[nx][ny]) continue;
            used[nx][ny]=true;
            if(dfs(board,word,index+1,nx,ny)) return true;
            used[nx][ny]=false;
        }
        return false;
    }
};